#include <assert.h>
#include <errno.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <sys/stat.h>

#include <dirent.h>
#include <fnmatch.h>
#include <glob.h>
#include <regex.h>

#include <err.h>
#include <sysexits.h>

#include "playlist.h"
#include "util.h"

#define PGDELTA 4

enum {
	PLCMPNORM,
	PLCMPGLOB,
	PLCMPBRE,
	PLCMPERE
};

enum {
	PEITEM,
	PEGRP
};

enum {
	PGNORM,
	PGSHUF,
	PGRAND
};

enum {
	PGLOST = 1
};

struct pentry;

struct pgroup {
	struct pgroup	*parent;
	struct pentry	**entries;
	size_t		 size;
	size_t		 count;
	size_t		 index;
	int		 flags;
	int		 type;
};

struct pitem {
	char		*path;
};

union punion {
	struct pgroup	 g;
	struct pitem	 e;
};

struct pentry {
	int		 type;
	union punion	 u;
};

struct hlist {
	struct pitem	**entries;
	size_t		 size;
	size_t		 begin;
	size_t		 end;
	size_t		 index;
	int		 lost;
};

struct playlist {
	struct hlist	 hl;
	struct pgroup	 pg;
	struct pgroup	*ag;
	void		(*onadd)(void *, const char *);
	void		(*onrem)(void *, const char *);
	void		*addctx;
	void		*remctx;
	int		 flags;
};

static void		 pe_free(struct pentry *);

static void		*plcmp_init(const char *, int);
static void		 plcmp_fini(void *, int);
static int		 plcmp_call(void *, const char *, int);

static struct pitem	*pl_next(struct playlist *, struct pgroup *);
static void		 pl_rem(struct playlist *, struct pgroup *,
			    void *, int, void(*)(void *, const char *),
			    void *);
static int		 pl_remove(struct playlist *, struct pgroup *,
			    size_t, void(*)(void *, const char *),
			    void *);

static void		 pg_init(struct pgroup *, int);
static void		 pg_fini(struct pgroup *);
static void		 pg_append(struct pgroup *, struct pentry *);
static struct pitem	*pg_current(struct pgroup *);
static struct pgroup	*pg_parent(struct pgroup *, struct pitem *);
static void		 pg_reset(struct pgroup *);
static struct pitem	*pg_search(struct pgroup *, void *, int, int);
static int		 pg_goto(struct pgroup *, struct pitem *);

static void		 hl_init(struct hlist *, size_t);
static void		 hl_fini(struct hlist *);
static void		 hl_append(struct hlist *, struct pitem *);
static int		 hl_remove(struct hlist *, struct pitem *);
static void		 hl_rem(struct hlist *, void *, int);
static struct pitem	*hl_current(struct hlist *);
static struct pitem	*hl_next(struct hlist *);
static struct pitem	*hl_prev(struct hlist *);
static struct pitem	*hl_search(struct hlist *, void *, int);
static int		 hl_goto(struct hlist *, struct pitem *);

static int		 pl_gtype(int);
static int		 pl_stype(int);

static int		 de_nodot(const struct dirent *);

struct playlist *
playlist_create(size_t hsize, int flags)
{
	struct playlist *pl;

	if ((pl = malloc(sizeof(*pl))) == NULL)
		err(EX_OSERR, "playlist_create");
	hl_init(&pl->hl, hsize);
	if ((flags & PLGTYPE) == PLGNONE)
		flags = (flags & ~PLGTYPE) | PLGNORM;
	pg_init(&pl->pg, pl_gtype(flags));
	pl->ag = &pl->pg;
	pl->flags = flags;
	pl->onadd = NULL;
	pl->onrem = NULL;
	pl->addctx = NULL;
	pl->remctx = NULL;
	return (pl);
}

void
playlist_destroy(struct playlist *pl)
{

	assert(pl != NULL);
	hl_fini(&pl->hl);
	pg_fini(&pl->pg);
	free(pl);
}

void
playlist_loop(struct playlist *pl)
{

	assert(pl != NULL);
	pg_reset(&pl->pg);
}

void
playlist_onadd(struct playlist *pl, void (*cb)(void *, const char *),
    void *ctx)
{

	assert(pl != NULL);
	pl->onadd = cb;
	pl->addctx = ctx;
}

void
playlist_onrem(struct playlist *pl, void (*cb)(void *, const char *),
    void *ctx)
{

	assert(pl != NULL);
	pl->onrem = cb;
	pl->remctx = ctx;
}

void
playlist_gbegin(struct playlist *pl, int flags)
{
	struct pentry *e;

	assert(pl != NULL);
	if ((flags & PLGTYPE) == PLGNONE)
		flags = (flags & ~PLGTYPE) | (pl->flags & PLGTYPE);
	if ((e = malloc(sizeof(*e))) == NULL)
		err(EX_OSERR, "playlist_gbegin");
	e->type = PEGRP;
	pg_init(&e->u.g, pl_gtype(flags));
	pg_append(pl->ag, e);
	pl->ag = &e->u.g;
}

int
playlist_gend(struct playlist *pl)
{

	assert(pl != NULL && pl->ag != NULL);
	if (pl->ag->parent == NULL)
		return (-1);
	pl->ag = pl->ag->parent;
	return (0);
}

void
playlist_append(struct playlist *pl, const char *path)
{
	struct pentry *e;

	assert(pl != NULL && path != NULL);
	if ((e = malloc(sizeof(*e))) == NULL)
		err(EX_OSERR, "playlist_append");
	e->type = PEITEM;
	if ((e->u.e.path = strdup(path)) == NULL)
		err(EX_OSERR, "playlist_append");
	pg_append(pl->ag, e);
	if (pl->onadd != NULL)
		pl->onadd(pl->addctx, e->u.e.path);
}

int
playlist_add(struct playlist *pl, const char *pat, int flags)
{
	struct dirent **de;
	struct stat st;
	glob_t gl;
	char *s;
	size_t i;
	int l;
	int n;
	int g;

	assert(pl != NULL && pat != NULL);
	if ((flags & PLSTYPE) == PLSAUTO)
		flags = (flags & ~PLSTYPE) | ((pl->flags & PLSTYPE)
		    == PLSAUTO ? PLSCMP : (pl->flags & PLSTYPE));
	if ((g = (flags & PLGTYPE) != PLGNONE))
		playlist_gbegin(pl, pl_gtype(flags));
	flags = (flags & ~PLGTYPE) | PLGNONE;
	switch (flags & PLSTYPE) {
	case PLSCMP:
		if (stat(pat, &st) != 0)
			return (-1);
		if ((flags & PLRTYPE) != PLRNONE &&
		    S_ISDIR(st.st_mode)) {
			for (l = strlen(pat); pat[l - 1] == '/'; l--)
				/* do nothing */;
			if ((n = scandir(pat, &de, &de_nodot,
			    &alphasort)) < 0)
				return (-1);
			for (i = 0; i < n; i++) {
				if ((s = malloc(l +
				    strlen(de[i]->d_name) + 2)) == NULL)
					err(EX_OSERR, "playlist_add");
				(void)sprintf(s, "%.*s/%s", l, pat,
				    de[i]->d_name);
				(void)playlist_add(pl, s,
				    (flags & PLRTYPE) != PLRFULL ?
				    ((flags & ~PLRTYPE) | PLRNONE) :
				    flags);
				free(s);
				free(de[i]);
			}
			free(de);
		} else if (S_ISREG(st.st_mode)) {
			playlist_append(pl, pat);
		} else
			return (-1);
		break;
	case PLSGLOB:
		if (glob(pat, 0, NULL, &gl) != 0)
			return (-1);
		for (i = 0; i < gl.gl_pathc; i++)
			playlist_add(pl, gl.gl_pathv[i],
			    (flags & ~PLSTYPE) | PLSCMP);
		globfree(&gl);
		break;
	case PLSBRE:
		/* FALLTHROUGH */
	case PLSERE:
		errno = EINVAL;
		return (-1);
	default:
		abort();
	}
	return (g ? playlist_gend(pl) : 0);
}

int
playlist_rem(struct playlist *pl, const char *pat, int flags)
{
	void *cmp;
	int s;

	assert(pl != NULL && pat != NULL);
	if ((flags & PLSTYPE) == PLSAUTO)
		flags = (flags & ~PLSTYPE) | ((pl->flags & PLSTYPE)
		    == PLSAUTO ? PLSGLOB : (pl->flags & PLSTYPE));
	s = pl_stype(flags);
	if ((cmp = plcmp_init(pat, s)) == NULL)
		return (-1);
	hl_rem(&pl->hl, cmp, s);
	pl_rem(pl, &pl->pg, cmp, s, pl->onrem, pl->remctx);
	plcmp_fini(cmp, s);
	return (playlist_current(pl) != NULL ? 0 : 1);
}

const char *
playlist_current(struct playlist *pl)
{
	struct pitem *e;

	assert(pl != NULL);
	if (pl->hl.lost)
		return (NULL);
	if ((e = hl_current(&pl->hl)) != NULL)
		return (e->path);
	if ((e = pg_current(&pl->pg)) != NULL)
		return (e->path);
	return (NULL);
}

const char *
playlist_next(struct playlist *pl)
{
	struct pitem *e;
	int l;

	assert(pl != NULL);
	l = hl_current(&pl->hl) != NULL || pl->hl.lost;
	if ((e = hl_next(&pl->hl)) != NULL)
		return (e->path);
	if ((e = pg_current(&pl->pg)) != NULL) {
		if (l)
			return (e->path);
		hl_append(&pl->hl, e);
	}
	if ((e = pl_next(pl, &pl->pg)) != NULL)
		return (e->path);
	return (NULL);
}

const char *
playlist_prev(struct playlist *pl)
{
	struct pitem *e;

	assert(pl != NULL);
	if ((e = hl_prev(&pl->hl)) != NULL)
		return (e->path);
	return (NULL);
}

const char *
playlist_search(struct playlist *pl, const char *pat, int flags)
{
	struct pgroup *pg;
	struct pitem *e;
	void *cmp;
	int s;

	assert(pl != NULL && pat != NULL);
	s = pl_stype(flags);
	if ((cmp = plcmp_init(pat, s)) == NULL)
		return (NULL);
	if ((e = hl_search(&pl->hl, cmp, s)) != NULL) {
		if (flags & PLGOTO)
			(void)hl_goto(&pl->hl, e);
	} else if ((e = pg_search(&pl->pg, cmp, s, flags & PLLOOP))
	    != NULL) {
		if ((flags & PLGOTO) && pg_goto(&pl->pg, e) != 0) {
			pg_reset(&pl->pg);
			(void)pg_goto(&pl->pg, e);
			pg = pg_parent(&pl->pg, e);
			assert(pg != NULL);
			if (pg->type == PGSHUF) {
				memswap(&pg->entries[0],
				    &pg->entries[pg->index],
				    sizeof(pg->entries[0]));
				e = &pg->entries[0]->u.e;
				pg->index = 0;
			}
		}
	}
	plcmp_fini(cmp, s);
	return (e != NULL ? e->path : NULL);
}

void
pe_free(struct pentry *e)
{

	assert(e != NULL);
	switch (e->type) {
	case PEITEM:
		free(e->u.e.path);
		break;
	case PEGRP:
		pg_fini(&e->u.g);
		break;
	default:
		abort();
	}
	free(e);
}

void *
plcmp_init(const char *pat, int type)
{
	regex_t *r;

	assert(pat != NULL);
	switch(type) {
	case PLCMPNORM:
		/* FALLTHROUGH */
	case PLCMPGLOB:
		return (strdup(pat));
	case PLCMPBRE:
		/* FALLTHROUGH */
	case PLCMPERE:
		if ((r = malloc(sizeof(*r))) == NULL)
			return (NULL);
		if (regcomp(r, pat, REG_NOSUB | (type == PLCMPERE ?
		    REG_EXTENDED : REG_BASIC)) != 0) {
			free(r);
			return (NULL);
		}
		return (r);
	}
	abort();
}

void
plcmp_fini(void *cmp, int type)
{

	switch(type) {
	case PLCMPNORM:
		return;
	case PLCMPGLOB:
		return;
	case PLCMPBRE:
		/* FALLTHROUGH */
	case PLCMPERE:
		regfree(cmp);
		break;
	}
	abort();
}

int
plcmp_call(void *cmp, const char *str, int type)
{

	assert(cmp != NULL);
	switch(type) {
	case PLCMPNORM:
		return (strcmp(cmp, str));
	case PLCMPGLOB:
		return (fnmatch(cmp, str, 0));
	case PLCMPBRE:
		/* FALLTHROUGH */
	case PLCMPERE:
		return (regexec(cmp, str, 0, NULL, 0));
	}
	abort();
}

struct pitem *
pl_next(struct playlist *pl, struct pgroup *pg)
{
	struct pitem *e;

	assert(pl != NULL && pg != NULL);
	if (pg->index >= pg->count && pg->type != PGRAND)
		return (NULL);
	if (!(pg->flags & PGLOST) && pg->index < pg->count &&
	    pg->entries[pg->index]->type == PEGRP &&
	    pg->entries[pg->index]->u.g.type != PGRAND) {
		if ((e = pl_next(pl, &pg->entries[pg->index]->u.g))
		    != NULL) {
			pg->flags &= ~PGLOST;
			return (e);
		}
		pg_reset(&pg->entries[pg->index]->u.g);
	}
	for (;;) {
		/* Select the next entry in this group */
		switch (pg->type) {
		case PGNORM:
			/* FALLTHROUGH */
		case PGSHUF:
			if (!(pg->flags & PGLOST) &&
			    pg->index < pg->count)
				pg->index++;
			break;
		case PGRAND:
			pg->index = arc4random_uniform(pg->count);
			break;
		default:
			abort();
		}
		if (pg->index >= pg->count)
			return (NULL);
		pg->flags &= ~PGLOST;
		if (pg->entries[pg->index]->type == PEITEM)
			return (&pg->entries[pg->index]->u.e);
		else if ((e = pl_next(pl, &pg->entries[pg->index]->u.g))
		    != NULL)
			return (e);
		else if (pg->entries[pg->index]->u.g.count > 0)
			pg_reset(&pg->entries[pg->index]->u.g);
		else
			pl_remove(pl, pg, pg->index, NULL, NULL);
	}
	return (NULL);
}

void
pl_rem(struct playlist *pl, struct pgroup *pg, void *cmp, int type,
    void (*cb)(void *, const char *), void *ctx)
{
	size_t i;

	assert(pl != NULL && pg != NULL && cmp != NULL);
	for (i = 0; i < pg->count; i++)
		switch (pg->entries[i]->type) {
		case PEITEM:
			if (plcmp_call(cmp, pg->entries[i]->u.e.path,
			    type) == 0)
				(void)pl_remove(pl, pg, i--, cb, ctx);
			break;
		case PEGRP:
			pl_rem(pl, &pg->entries[i]->u.g, cmp, type, cb,
			    ctx);
			if (pg->entries[i]->u.g.count == 0) {
				(void)pl_remove(pl, pg, i--, cb, ctx);
			}
			break;
		default:
			abort();
		}
}

int
pl_remove(struct playlist *pl, struct pgroup *pg, size_t index,
    void (*cb)(void *, const char *), void *ctx)
{

	assert(pg != NULL);
	if (index >= pg->count)
		return (-1);
	if (pg->entries[index]->type == PEITEM && cb != NULL)
		cb(ctx, pg->entries[index]->u.e.path);
	if (pg->entries[index]->type == PEGRP) {
		if (pl == NULL)
			return (-1);
		if (&pg->entries[index]->u.g == pl->ag)
			pl->ag = pg->entries[index]->u.g.parent;
	}
	pe_free(pg->entries[index]);
	if (index + 1 < pg->count)
		(void)memmove(&pg->entries[index],
		    &pg->entries[index + 1], sizeof(pg->entries[0]) *
		    (pg->count - index - 1));
	if (index == pg->index)
		pg->flags |= PGLOST;
	else if (index < pg->index)
		pg->index--;
	pg->count--;
	return (0);
}

void
pg_init(struct pgroup *pg, int type)
{

	assert(pg != NULL);
	pg->parent = NULL;
	pg->entries = NULL;
	pg->size = 0;
	pg->count = 0;
	pg->index = 0;
	pg->flags = PGLOST;
	pg->type = type;
}

void
pg_fini(struct pgroup *pg)
{

	assert(pg != NULL);
	while (pl_remove(NULL, pg, 0, NULL, NULL) == 0)
		/* do nothing */;
	if (pg->entries != NULL)
		free(pg->entries);
	pg_init(pg, pg->type);
}

void
pg_append(struct pgroup *pg, struct pentry *e)
{

	assert(pg != NULL && e != NULL);
	*(struct pentry **)allot((void **)&pg->entries, &pg->size,
	    pg->count, sizeof(e), PGDELTA) = e;
	if (e->type == PEGRP)
		e->u.g.parent = pg;
	pg->count++;
	if (pg->type == PGSHUF && pg->count > pg->index) {
		if ((pg->flags & PGLOST) && pg->count - pg->index > 2)
			memshuffle(pg->entries + pg->index,
			    pg->count - pg->index,
			    sizeof(pg->entries[0]));
		else if (pg->count - pg->index >= 2)
			memshuffle(pg->entries + pg->index + 1,
			    pg->count - pg->index - 1,
			    sizeof(pg->entries[0]));
	}
}

struct pitem *
pg_current(struct pgroup *pg)
{

	assert(pg != NULL);
	if ((pg->flags & PGLOST) || pg->index >= pg->count)
		return (NULL);
	switch (pg->entries[pg->index]->type) {
	case PEITEM:
		return (&pg->entries[pg->index]->u.e);
	case PEGRP:
		return (pg_current(&pg->entries[pg->index]->u.g));
	}
	abort();
}

struct pgroup *
pg_parent(struct pgroup *pg, struct pitem *e)
{
	struct pgroup *r;
	size_t i;

	assert(pg != NULL && e != NULL);
	for (i = 0; i < pg->count; i++)
		switch (pg->entries[i]->type) {
		case PEITEM:
			if (&pg->entries[i]->u.e == e)
				return (pg);
			break;
		case PEGRP:
			if ((r = pg_parent(&pg->entries[i]->u.g, e))
			    != NULL)
				return (r);
			break;
		default:
			abort();
		}
	return (NULL);
}

void
pg_reset(struct pgroup *pg)
{
	size_t i;

	assert(pg != NULL);
	if (pg->count == 0)
		return;
	for (i = 0; i < pg->count; i++)
		if (pg->entries[i]->type == PEGRP)
			pg_reset(&pg->entries[i]->u.g);
	pg->index = 0;
	switch (pg->type) {
	case PGNORM:
		break;
	case PGSHUF:
		memshuffle(pg->entries, pg->count,
		    sizeof(pg->entries[0]));
		break;
	case PGRAND:
		break;
	default:
		abort();
	}
	pg->flags |= PGLOST;
}

struct pitem *
pg_search(struct pgroup *pg, void *cmp, int type, int loop)
{
	struct pitem *r = NULL;
	struct pitem *e;
	size_t i;
	size_t n;

	assert(pg != NULL && cmp != NULL);
	switch (pg->type) {
	case PGNORM:
		/* FALLTHROUGH */
	case PGSHUF:
		for (i = pg->index; i < pg->count; i++)
			switch (pg->entries[i]->type) {
			case PEITEM:
				if (i == pg->index)
					break;
				if (plcmp_call(cmp,
				    pg->entries[i]->u.e.path, type)
				    == 0)
					return (&pg->entries[i]->u.e);
				break;
			case PEGRP:
				if ((r = pg_search(&pg->entries[i]->u.g,
				    cmp, type, loop)) != NULL)
					return (r);
				break;
			default:
				abort();
			}
		if (!loop)
			break;
		if (pg->type == PGSHUF)
			goto rand;
		for (i = 0; i < pg->index; i++)
			switch (pg->entries[i]->type) {
			case PEITEM:
				if (plcmp_call(cmp,
				    pg->entries[i]->u.e.path, type)
				    == 0)
					return (&pg->entries[i]->u.e);
				break;
			case PEGRP:
				if ((r = pg_search(&pg->entries[i]->u.g,
				    cmp, type, loop)) != NULL)
					return (r);
				break;
			default:
				abort();
			}
		break;
	case PGRAND:
	rand:
		for (i = 0, n = 1; i < pg->count; i++) {
			e = NULL;
			switch (pg->entries[i]->type) {
			case PEITEM:
				if (plcmp_call(cmp,
				    pg->entries[i]->u.e.path, type)
				    == 0)
					e = &pg->entries[i]->u.e;
				break;
			case PEGRP:
				e = pg_search(&pg->entries[i]->u.g, cmp,
				    type, loop);
				break;
			default:
				abort();
			}
			if (e != NULL && (n == 1 ||
			    arc4random_uniform(n) == 0)) {
				r = e;
				n++;
			}
		}
		break;
	default:
		abort();
	}
	return (r);
}

int
pg_goto(struct pgroup *pg, struct pitem *e)
{

	assert(pg != NULL && e != NULL);
	if (pg->type == PGRAND)
		pg->index = 0;
	for (; pg->index < pg->count; pg->index++)
		switch (pg->entries[pg->index]->type) {
		case PEITEM:
			if (&pg->entries[pg->index]->u.e == e)
				return (0);
			break;
		case PEGRP:
			if (pg_goto(&pg->entries[pg->index]->u.g, e)
			    == 0)
				return (0);
			break;
		default:
			abort();
		}
	return (-1);
}

void
hl_init(struct hlist *hl, size_t size)
{

	assert(hl != NULL);
	assert(SIZE_MAX / size >= sizeof(hl->entries[0]));
	if (size > 0) {
		if ((hl->entries =
		    malloc(size * sizeof(hl->entries[0]))) == NULL)
			err(EX_OSERR, "hl_init");
	} else
		hl->entries = NULL;
	hl->size = size;
	hl->begin = 0;
	hl->end = 0;
	hl->index = 0;
	hl->lost = 0;
}

void
hl_fini(struct hlist *hl)
{

	assert(hl != NULL);
	while (hl_remove(hl, hl->entries[hl->begin]) == 0)
		/* do nothing */;
	if (hl->entries != NULL) {
		free(hl->entries);
		hl->entries = NULL;
	}
	hl->size = 0;
	hl->begin = 0;
	hl->end = 0;
	hl->index = 0;
	hl->lost = 0;
}

void
hl_append(struct hlist *hl, struct pitem *e)
{

	assert(hl != NULL);
	if (hl->size == 0)
		return;
	assert(hl->index != hl->begin ||
	    (hl->end + 1) % hl->size != hl->begin);
	hl->entries[hl->end] = e;
	if (hl->index == hl->end)
		hl->index = (hl->index + 1) % hl->size;
	hl->end = (hl->end + 1) % hl->size;
	if (hl->end == hl->begin)
		hl->begin = (hl->begin + 1) % hl->size;
}

int
hl_remove(struct hlist *hl, struct pitem *e)
{
	size_t i;
	size_t j;

	assert(hl != NULL);
	for (i = hl->begin, j = hl->begin; i != hl->end;
	    i = (i + 1) % hl->size)
		if (hl->entries[i] == e) {
			if (i == hl->index)
				hl->lost = 1;
			if (i + (i < hl->begin ? hl->size : 0) <
			    hl->index + (hl->index < hl->begin ?
			    hl->size : 0) || hl->index == hl->end)
				hl->index = (hl->index + hl->size - 1) %
				    hl->size;
		} else {
			hl->entries[j] = hl->entries[i];
			j = (j + 1) % hl->size;
		}
	hl->end = j;
	if (hl->index + (hl->index < hl->begin ? hl->size : 0) >
	    hl->end + (hl->end < hl->begin ? hl->size : 0))
		hl->index = hl->end;
	return (i != j ? 0 : -1);
}

void
hl_rem(struct hlist *hl, void *cmp, int type)
{
	size_t i;

	assert(hl != NULL && cmp != NULL);
	for (i = hl->begin; i != hl->end; i = (i + 1) % hl->size)
		if (plcmp_call(cmp, hl->entries[i]->path, type) == 0) {
			(void)hl_remove(hl, hl->entries[i]);
			i = (i + hl->size - 1) % hl->size;
		}
}

struct pitem *
hl_current(struct hlist *hl)
{

	assert(hl != NULL);
	if (hl->lost || hl->index == hl->end)
		return (NULL);
	return (hl->entries[hl->index]);
}

struct pitem *
hl_next(struct hlist *hl)
{

	assert(hl != NULL);
	if (hl->index == hl->end)
		goto ret;
	if (!hl->lost)
		hl->index = (hl->index + 1) % hl->size;
ret:
	hl->lost = 0;
	return (hl->index != hl->end ? hl->entries[hl->index] : NULL);
}

struct pitem *
hl_prev(struct hlist *hl)
{

	assert(hl != NULL);
	hl->lost = 0;
	if (hl->index == hl->begin)
		return (NULL);
	hl->index = (hl->index + hl->size - 1) % hl->size;
	return (hl->entries[hl->index]);
}

struct pitem *
hl_search(struct hlist *hl, void *cmp, int type)
{
	size_t i;

	assert(hl != NULL && cmp != NULL);
	for (i = hl->index; i != hl->end; i = (i + 1) % hl->size)
		if (plcmp_call(cmp, hl->entries[i]->path, type) == 0)
			return (hl->entries[i]);
	return (NULL);
}

int
hl_goto(struct hlist *hl, struct pitem *e)
{

	for (; hl->index != hl->end;
	    hl->index = (hl->index + 1) % hl->size)
		if (hl->entries[hl->index] == e)
			return (0);
	return (-1);
}

int
pl_gtype(int flags)
{

	switch (flags & PLGTYPE) {
	case PLGNORM:
		return (PGNORM);
	case PLGSHUF:
		return (PGSHUF);
	case PLGRAND:
		return (PGRAND);
	}
	abort();
}

int
pl_stype(int flags)
{

	switch (flags & PLSTYPE) {
	case PLSAUTO:
		return (PLCMPGLOB);
	case PLSCMP:
		return (PLCMPNORM);
	case PLSGLOB:
		return (PLCMPGLOB);
	case PLSBRE:
		return (PLCMPBRE);
	case PLSERE:
		return (PLCMPERE);
	}
	abort();
}

int
de_nodot(const struct dirent *e)
{

	assert(e != NULL);
	return (strcmp(e->d_name, ".") != 0 &&
	    strcmp(e->d_name, "..") != 0);
}
